Sequences and Summations
Sets are unordered S = { a , b , ⋯ } S=\{a, b,\cdots\} S = { a , b , ⋯ } Sequences are ordered
prf:definition **Sequences**A **Sequence** is a function from a subset of the set of integers\
We use notation $a_n$ to denote the image of the integer $n$\
We call $a_n$ a **term** of the sequence
{bdg-success}`Formal Definition`
Let $S \subseteq \mathbb{Z}$ and suppose $S$ has a least element\
A sequence of numbers is the range of a function\
$f: S \rightarrow\text{ some number set}$
S S S { k , k + 1 , k + 2 , ⋯ } ⊆ Z \{k, k+1, k+2, \cdots\} \subseteq \mathbb{Z} { k , k + 1 , k + 2 , ⋯ } ⊆ Z
Here k = initial index (usually 0,1 ) k\text{ = initial index (usually 0,1 )} k = initial index (usually 0,1 )
The set of numbers is most often R = real numbers \mathbb{R}=\text{ real numbers} R = real numbers
a sequence then is r a n g e ( f ) = { f ( k ) , f ( k + 1 ) , f ( k + 2 ) , ⋯ } range(f)=\{f(k), f(k+1), f(k+2), \cdots\} r an g e ( f ) = { f ( k ) , f ( k + 1 ) , f ( k + 2 ) , ⋯ }
We usually wite a x = f ( n ) a_{x}=f(n) a x = f ( n ) n ⩾ k n \geqslant k n ⩾ k r a n g e ( f ) = { a k , a k + 1 , ⋯ , a n , ⋯ } = { a n } n = k N range(f)=\left\{a_{k}, a_{k+1}, \cdots, a_{n}, \cdots\right\}=\left\{a_{n}\right\}_{n=k}^{N} r an g e ( f ) = { a k , a k + 1 , ⋯ , a n , ⋯ } = { a n } n = k N a n a_{n} a n general term
( N ∈ Z (N \in Z ( N ∈ Z N = + ∞ ) N=+\infty) N = + ∞ )
S = index set S=\text{ index set} S = index set If S S S finite subset of Z \mathbb{Z} Z r a n g e ( f ) range(f) r an g e ( f ) finite sequence S S S infinite subset of Z \mathbb{Z} Z infinite sequence
There are some special sequences that often arise...
Geometric Progression
Here S = { 0 , 1 , 2 , ⋯ } = Z + ∪ { 0 } S=\{0,1,2, \cdots\}=\mathbb{Z}^{+} \cup\{0\} S = { 0 , 1 , 2 , ⋯ } = Z + ∪ { 0 } f ( n ) = a n = a r n w h e r e a , r ∈ R f(n)=a_{n}=a r^{n}\quad where\quad a,r\in\mathbb{R} f ( n ) = a n = a r n w h ere a , r ∈ R
The sequence is
{ a n } n = 0 + ∞ = { a , a ⋅ r , a ⋅ r 2 , a ⋅ r 3 , a ⋅ r 4 , ⋯ , a ⋅ r n , ⋯ }
\left\{a_{n}\right\}_{n=0}^{+\infty}=\left\{a, a \cdot r, a \cdot r^{2}, a \cdot r^{3}, a \cdot r^{4}, \cdots, a \cdot r^{n}, \cdots\right\}
{ a n } n = 0 + ∞ = { a , a ⋅ r , a ⋅ r 2 , a ⋅ r 3 , a ⋅ r 4 , ⋯ , a ⋅ r n , ⋯ } a a a initial term and r r r common ratio
prf:definition **Geometric Progression**This is a sequence of the form
$ a, ar, ar^2, \cdots , ar^n, \cdots $
```{prf:remark} Analogue to exponential functions
A geometric progression is a discrete analogue of the exponential function $f(x)=ar^x$
```
Geometric Series (Finite)
G_{n}&=a+a r+\cdots+a r^{n}\\
&=\sum_{k=0}^{n} a r^{k}= \begin{cases}\displaystyle{\frac{a\left(r^{n+1}-1\right)}{r-1}} &, r \neq 1 \\ (n+1)a &, r=1\end{cases}
Poof Case i) r = 1 r=1 r = 1
G n = ∑ k = 0 n a ( 1 ) k = ∑ k = 0 n a ( 1 ) = a ∑ k = 0 n ( 1 ) = a ( 1 + 1 + ⋯ + 1 ⏟ n + 1 terms = a ( n + 1 ) .
\begin{aligned}
G_{n}=\sum_{k=0}^{n} a(1)^{k}=\sum_{k=0}^{n} a(1)=a \sum_{k=0}^{n}(1) & =a(\underbrace{1+1+\cdots+1}_{n+1} \text { terms } \\
& =a(n+1) .
\end{aligned}
G n = k = 0 ∑ n a ( 1 ) k = k = 0 ∑ n a ( 1 ) = a k = 0 ∑ n ( 1 ) = a ( n + 1 1 + 1 + ⋯ + 1 terms = a ( n + 1 ) . Case ii) r ≠ 1 r \neq 1 r = 1
G n = a + a r + a r 2 + ⋯ + a r n r G n = a r + a r 2 + ⋯ + a r n + a r n + 1 ∴ r G n − G n = ( r − 1 ) G n = a r n + 1 − a = a ( r n + 1 − 1 ) . thus G n = a ( r n + 1 − 1 ) r − 1
\begin{aligned}
& G_{n}=a+a r+a r^{2}+\cdots+a r^{n} \\
& r G_{n}=a r+a r^{2}+\cdots+a r^{n}+a r^{n+1} \\
& \therefore r G_{n}-G_{n}=(r-1) G_{n}=a r^{n+1}-a=a\left(r^{n+1}-1\right) \text {. } \\
& \text { thus } G_{n}=\frac{a\left(r^{n+1}-1\right)}{r-1}
\end{aligned}
G n = a + a r + a r 2 + ⋯ + a r n r G n = a r + a r 2 + ⋯ + a r n + a r n + 1 ∴ r G n − G n = ( r − 1 ) G n = a r n + 1 − a = a ( r n + 1 − 1 ) . thus G n = r − 1 a ( r n + 1 − 1 )
prf:Theorem Geometric Sequences in GeneralIf $a$ and $r$ are real numbers and $r\ne 0$, then
$$
\displaystyle\sum^n_{j=0}ar^j = \begin{cases}
\displaystyle\frac{ar^{n+1}-a}{r-1}\quad &if\quad r\ne 1\\
\displaystyle(n+1)a\quad &if\quad r= 1\\
\end{cases}
$$
bdg-secondary proof
Let\qquad S_n&=\sum^n_{j=m}ar^j\\
To compute S S S r r r
rS_n&=r\sum^n_{j=0}ar^j\qquad\textcolor{hotpink}{\textrm{multiply both sides by $r$}}\\
&=\sum^n_{j=0}ar^{j+1}\qquad\textcolor{hotpink}{\textrm{by the distributive property}}\\
&=\sum^{n+1}_{k=1}ar^{k}\qquad\textcolor{hotpink}{\textrm{Shifting the index by $k=j+1$}}\\
&=ar^1 + ar^2 + ar^3 + , \cdots , ar^n + ar^{n+1}\\
&=\left(\sum^{n+1}_{k=1}ar^{k}\right)+(ar^{n+1}-a)\qquad\textcolor{hotpink}{\textrm{Isolate $n+1$ term but add $k=0$ term}}\\
&=S_n+(ar^{n+1}-a)\qquad\textcolor{hotpink}{\textrm{Substitute back S for the summation formula}}\\
We see thus that r S n = S n + ( a r n + 1 − a ) rS_n = S_n + (ar^{n+1}-a) r S n = S n + ( a r n + 1 − a ) S n S_n S n r ≠ 1 r\ne 1 r = 1 S n = a r n + 1 − a r − 1 \displaystyle S_n = \frac{ar^{n+1} - a}{r - 1} S n = r − 1 a r n + 1 − a
For r = 1 r=1 r = 1 S n = ∑ j = 0 n a r j = ∑ j = 0 n a S_n=\sum^n_{j=0}ar^j=\sum_{j=0}^na S n = ∑ j = 0 n a r j = ∑ j = 0 n a
Arithmetic Progression
Here S = { 0 , 1 , 2 , … } = Z + ∪ { 0 } S=\{0,1,2, \ldots\}=\mathbb{Z}^+ \cup\{0\} S = { 0 , 1 , 2 , … } = Z + ∪ { 0 } f ( n ) = a + n ⋅ d f(n)=a+n \cdot d f ( n ) = a + n ⋅ d a , d ∈ R a, d \in \mathbb{R} a , d ∈ R
{ a n } n = 0 + ∞ = { a , a + d , a + 2 d , ⋯ , a + n d , ⋯ }
\left\{a_{n}\right\}_{n=0}^{+\infty}=\{a, a+d, a+2 d, \cdots, a+n d, \cdots\}
{ a n } n = 0 + ∞ = { a , a + d , a + 2 d , ⋯ , a + n d , ⋯ } a is called the initial term and d d d common difference
prf:definition **Arithmetic Progression**This is a sequence of the form
$ a, a + d, a + 2d, \cdots , a + nd, \cdots$\
where the *initial term* $a$ and the *common difference* $d$ are *real numbers*
```{prf:remark} Analogue to linear functions
A arithmetic progression is a discrete analogue of the linear function $f(x)=dx + a$
```
Sequences of the form a 1 , a 2 , . . . , a n a_1, a_2, ... , a_n a 1 , a 2 , ... , a n strings denoted by a 1 a 2 . . . a n a_1 a_2 ... a_n a 1 a 2 ... a n length of a string is the number of terms in this string the empty string is denoted by λ \lambda λ
A n = ∑ k = 0 n ( a + d k ) = ( n + 1 ) ( 2 a + n d ) 2
A_{n}=\sum_{k=0}^{n}(a+d k)=\frac{(n+1)(2 a+n d)}{2}
A n = k = 0 ∑ n ( a + d k ) = 2 ( n + 1 ) ( 2 a + n d ) Poof
A n = ∑ k = 0 n ( a + d k ) = ∑ k = 0 n a + ∑ k = 0 n d k = a ∑ k = 0 n i + d ∑ k = 1 n k = ( n + 1 ) a + d ( ∑ k = 1 n k )
\begin{aligned}
A_{n} & =\sum_{k=0}^{n}(a+d k)=\sum_{k=0}^{n} a+\sum_{k=0}^{n} d k \\
& =a \sum_{k=0}^{n} i+d \sum_{k=1}^{n} k \\
& =(n+1) a+d\left(\sum_{k=1}^{n} k\right)
\end{aligned}
A n = k = 0 ∑ n ( a + d k ) = k = 0 ∑ n a + k = 0 ∑ n d k = a k = 0 ∑ n i + d k = 1 ∑ n k = ( n + 1 ) a + d ( k = 1 ∑ n k ) Fact
∑ k = 1 n k = 1 + 2 + ⋯ + n = n ( n + 1 ) 2
\sum_{k=1}^{n} k=1+2+\cdots+n=\frac{n(n+1)}{2}
k = 1 ∑ n k = 1 + 2 + ⋯ + n = 2 n ( n + 1 ) Thus
A n = ( n + 1 ) a + d n ( n + 1 ) 2 = ( n + 1 ) ( 2 a + n d ) 2
\begin{aligned}
A_{n} & =(n+1) a+d \frac{n(n+1)}{2} \\
& =\frac{(n+1)(2 a+n d)}{2}
\end{aligned}
A n = ( n + 1 ) a + d 2 n ( n + 1 ) = 2 ( n + 1 ) ( 2 a + n d ) Harmonic Progression
Here S = { 1 , 2 , ⋯ } = Z + S=\{1, 2, \cdots\}=\mathbb{Z}^+ S = { 1 , 2 , ⋯ } = Z + f ( n ) = 1 n f(n)=\frac{1}{n} f ( n ) = n 1
{ a n } n = 1 ∞ = { 1 , 1 2 , 1 3 , ⋯ , 1 n , ⋯ }
\left\{a_{n}\right\}_{n=1}^{\infty}=\left\{1, \frac{1}{2}, \frac{1}{3}, \cdots, \frac{1}{n}, \cdots\right\}
{ a n } n = 1 ∞ = { 1 , 2 1 , 3 1 , ⋯ , n 1 , ⋯ }
prf:example **Harmonic Set**Consider the sequence $a_n$, where $a_n=1/n$\
The list of the of this sequence, beginning with $a_1$, namely\
$a_1, a_2, a_3, a_4,\cdots,$
$$
1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots,
$$
Recurrence Relation
Before we specified sequences by providing explicit formulas for their termsbut there are other ways to specify a sequence
prf:definition **Recurrence Relation**A **recurrence relation** for the sequence $\Set{a+n}$ is an equation that expresses $a_n$ in terms of one or more of the previous terms of the sequences, namely for all integers $n\ge n_0$ where $n_0$ is a nonnegative integer.
> A sequence is called a **solution** of a recurrence relation if its terms satisfy the recurrence relation
Some useful Sequences
Summations
a m , a ( m + 1 ) , ⋯ , a n a_m,a_(m+1),\cdots ,a_n a m , a ( m + 1 ) , ⋯ , a n \Set a n \Set{a_n} \Set a n
We use the notation
∑ j = m n a j = ∑ j = m n a j = ∑ m ≤ j ≤ n n a j
\displaystyle\sum^n_{j=m}a_j = \textstyle\sum^n_{j=m}a_j = \displaystyle\sum^n_{m\ \le j\ \le\ n}a_j
j = m ∑ n a j = ∑ j = m n a j = m ≤ j ≤ n ∑ n a j reads as the sum from j = m to j = n of a j \textit{sum from j = m to j = n of }a_j sum from j = m to j = n of a j
Variable j j j index of summation or dummy index you can define it as any variable as below shows
∑ j = m n a j = ∑ i = m n a i = ∑ k = m n a k
\sum^n_{j=m}a_j = \sum^n_{i=m}a_i = \sum^n_{k=m}a_k
j = m ∑ n a j = i = m ∑ n a i = k = m ∑ n a k Variable m m m lower limit or the initial index n n n upper limit or terminal index
Sum
Closed Form
∑ k = 0 n a r k ( r ≠ 0 ) \displaystyle{\sum^n_{k=0}ar^k\ (r\ne 0)} k = 0 ∑ n a r k ( r = 0 ) ref proofa r n + 1 − a r − 1 \displaystyle{\frac{ar_{n+1}-a}{r-1}} r − 1 a r n + 1 − a
∑ k = 1 n k \displaystyle{\sum^n_{k=1}k} k = 1 ∑ n k n ( n + 1 ) 2 \displaystyle{\frac{n(n+1)}{2}} 2 n ( n + 1 )
∑ k = 2 n k 2 \displaystyle{\sum^n_{k=2}k^2} k = 2 ∑ n k 2 n ( n + 1 ) ( 2 n + 1 ) 6 \displaystyle{\frac{n(n+1)(2n+1)}{6}} 6 n ( n + 1 ) ( 2 n + 1 )
∑ k = 2 n k 3 \displaystyle{\sum^n_{k=2}k^3} k = 2 ∑ n k 3 n 2 ( n + 1 ) 2 4 \displaystyle{\frac{n^2(n+1)^2}{4}} 4 n 2 ( n + 1 ) 2
∑ k = 0 ∞ x k , ∣ x ∣ < 1 \displaystyle{\sum^\infty_{k=0}x^k, \mid x\mid \lt 1} k = 0 ∑ ∞ x k , ∣ x ∣< 1 1 1 − x \displaystyle{\frac{1}{1-x}} 1 − x 1
∑ k = 1 ∞ x k , ∣ x ∣ < 1 \displaystyle{\sum^\infty_{k=1}x^k, \mid x\mid \lt 1} k = 1 ∑ ∞ x k , ∣ x ∣< 1 1 ( 1 − x ) 2 \displaystyle{\frac{1}{(1-x)^2}} ( 1 − x ) 2 1
Double Sums
Sometimes we want to sum a matrix of numbersdouble sum
( a 11 a 12 ⋯ a 1 n ⋮ ⋮ ⋯ ⋮ a n 1 a n 2 ⋯ a n n ) ∑ k , l = 1 n a k l = ∑ k = 1 n ∑ l = 1 n a k l So first sum all l terms then sum all k terms Ex ∑ k = 1 3 ∑ l = 2 4 ( k + 1 ) l 2 = ∑ k = 1 3 { ( k + 1 ) 4 + ( k + 1 ) 9 + ( k + 1 ) 16 } = ∑ k = 1 3 29 ( k + 1 ) = 29 ( ∑ k = 1 3 ( k + 1 ) ) = 29 [ 2 + 3 + 4 ] = 29 × 9 = 261
\begin{pmatrix}
a_{11} &a_{12} &\cdots& &a_{1n} \\
\vdots &\vdots &\cdots& &\vdots \\
a_{n1} &a_{n2} &\cdots& &a_{nn} \\
\end{pmatrix}\\
\newline
\sum^n_{k,l=1}a_{kl}\quad =\quad \sum^n_{k=1}\sum^n_{l=1}a_{kl}
\newline
\newline
\color{violet}{\text{So first sum all $l$ terms then sum all $k$ terms}}\\
\begin{aligned}
& \text { Ex } \quad \sum_{k=1}^3 \sum_{l=2}^4(k+1) l^2 \\
&=\sum_{k=1}^3\{(k+1) 4+(k+1) 9+(k+1) 16\} \\
&=\sum_{k=1}^3 29(k+1)=29\left(\sum_{k=1}^3(k+1)\right) \\
&=29[2+3+4]=29 \times 9=261
\end{aligned}
⎝ ⎛ a 11 ⋮ a n 1 a 12 ⋮ a n 2 ⋯ ⋯ ⋯ a 1 n ⋮ a nn ⎠ ⎞ k , l = 1 ∑ n a k l = k = 1 ∑ n l = 1 ∑ n a k l So first sum all l terms then sum all k terms Ex k = 1 ∑ 3 l = 2 ∑ 4 ( k + 1 ) l 2 = k = 1 ∑ 3 {( k + 1 ) 4 + ( k + 1 ) 9 + ( k + 1 ) 16 } = k = 1 ∑ 3 29 ( k + 1 ) = 29 ( k = 1 ∑ 3 ( k + 1 ) ) = 29 [ 2 + 3 + 4 ] = 29 × 9 = 261 Note
Sometimes we don't explicitly state s or sometimes S S S contiguous set of integers, for example S = \set 1 , 3 , 27 , 413 , 999 , 1 0 6 , 1 0 2 5 S=\set{1,3,27,413,999,10^6,10^25} S = \set 1 , 3 , 27 , 413 , 999 , 1 0 6 , 1 0 2 5 We can still us summation
∑ k ∈ S a k o r ∑ k ∈ S f ( k )
\displaystyle\sum_{k\in S}a_k\quad or\quad \sum_{k\in S}f(k)
k ∈ S ∑ a k or k ∈ S ∑ f ( k ) Special Finite Arithmetic Sequence
(1) ∑ k = 1 n k = n ( n + 1 ) 2 = 1 + 2 + ⋯ + n \displaystyle\sum_{k=1}^{n} k=\frac{n(n+1)}{2}=1+2+\cdots+n k = 1 ∑ n k = 2 n ( n + 1 ) = 1 + 2 + ⋯ + n
Proof: ∑ k = 0 n ( a + d k ) \sum_{k=0}^{n}(a+dk) ∑ k = 0 n ( a + d k )
prf:theorem Finite Arithmetic Sequences in General
$$
A_n = \sum^n_{k=1}(a+dk) = \frac{(n+1)(2a+nd)}{2}
$$
----------
{bdg-secondary}`Proof`
$$
A_n &=\sum^n_{k=1}(a+dk)\\
&=\sum^n_{k=1}a + \sum^n_{k=1}dk\\
&=a\sum^n_{k=1}1 + d\sum^n_{k=1}k\\
&=(n+1)a + d\sum^n_{k=1}k\\
&=(n+1)a + d\left(\frac{2(n+1)}{2}\right)\\
&=\frac{(n+1)(2a+nd)}{2}
$$
```{note}
We will prove $\displaystyle \sum^n_{k=1}k = 1+2+3+\cdots+n = \frac{2(n+1)}{2}$ later
```
Proof: ∑ k = 1 n k \sum_{k=1}^{n}k ∑ k = 1 n k
This is a Arithmetic Sequence
S=\text{Let }\sum^n_{k=1} &= 1+2+3+\cdots+(n-1)+n\\
\text{(backwards) }S &= n + (n-1) + (n-2) + \cdots + 2 + 1\\
\newline
\therefore \quad 2 S &=(n+1)+(n+1)+\cdots+(n+1)(n \text { terms }) \\
& =n(n+1) \\
\newline
\therefore\ \quad S &=\frac{n(n+1)}{2}
(2) ∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 = 1 + 4 + 9 + ⋯ + n 2 \displaystyle\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}=1+4+9+\cdots+n^{2} k = 1 ∑ n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) = 1 + 4 + 9 + ⋯ + n 2
(3) ∑ k = 1 n k 3 = [ n ( n + 1 ) 2 ] 2 = 1 + 8 + 27 + ⋯ + n 3 \displaystyle\sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}=1+8+27+\cdots+n^{3} k = 1 ∑ n k 3 = [ 2 n ( n + 1 ) ] 2 = 1 + 8 + 27 + ⋯ + n 3
bdg-danger Laterprinciple of mathematical induction
Infinite Series
Infinite series are important in many branches of mathematics, especially mathematical analysis
An infinite series is a summation of an infinite number of terms
Actually the sum of an infinite number of terms is not defined
However we can talk about these infinite sums in the context of wether or not they converge to a sum by looking at the sequence of partial sums
Let { a n } n = 0 + ∞ \left\{a_{n}\right\}_{n=0}^{+\infty} { a n } n = 0 + ∞
Let { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞ { a n } n = 0 + ∞ \left\{a_{n}\right\}_{n=0}^{+\infty} { a n } n = 0 + ∞
s n = ∑ k = 0 n a k = a 0 + a 1 + ⋯ + a n
s_{n}=\sum_{k=0}^{n} a_{k}=a_{0}+a_{1}+\cdots+a_{n}
s n = k = 0 ∑ n a k = a 0 + a 1 + ⋯ + a n Before we go any further we must talk about the limit of a sequence
Let { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞
We say { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞ L L L
or
lim n → + ∞ S n = L iff ∀ ε > 0 , ∃ N ( ε ) ∈ Z + such that ∣ S n − L ∣ < ε , ∀ n ⩾ N
\begin{aligned}
& \displaystyle\lim _{n \rightarrow+\infty} S_{n}=L \quad \text { iff }\\
\newline
& \forall \varepsilon>0,\quad\exists N(\varepsilon) \in \mathbb{Z}^{+} \text { such that}\\
& \left|S_{n}-L\right|<\varepsilon,\quad \forall n \geqslant N
\end{aligned}
n → + ∞ lim S n = L iff ∀ ε > 0 , ∃ N ( ε ) ∈ Z + such that ∣ S n − L ∣ < ε , ∀ n ⩾ N What this means is that the larger that n n n s n s_{n} s n L L L S n → L S_{n} \rightarrow L S n → L x → + ∞ x \rightarrow+\infty x → + ∞
If there is no number L L L S x → L S_{x} \rightarrow L S x → L n → + ∞ n \rightarrow+\infty n → + ∞ { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞
( 12 ) (12) ( 12 )
Two important limits
(1) lim n → + ∞ x n = 0 \displaystyle\lim _{n \rightarrow+\infty} x^{n}=0 n → + ∞ lim x n = 0 ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1
(2) lim n → + ∞ 1 n = 0 \displaystyle\lim _{n \rightarrow+\infty} \frac{1}{n}=0 n → + ∞ lim n 1 = 0
We have already discussed (2) before with the calculator if n becomes large enough the answer converges to 0
We prove (1) using Bernoulli's inequality
1 + n h ⩽ ( 1 + h ) n , ∀ n = 0 , 1 , 2 , … , h > − 1
\begin{gathered}
1+nh \leqslant(1+h)^{n},\quad \forall n=0,1,2, \ldots,\quad h>-1
\end{gathered}
1 + nh ⩽ ( 1 + h ) n , ∀ n = 0 , 1 , 2 , … , h > − 1 We will see a proof of this inequality later by proof by mathematical induction
lim n → + ∞ 1 n = 0 \displaystyle\lim _{n \rightarrow+\infty} \frac{1}{n}=0 n → + ∞ lim n 1 = 0 ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1 Proof by Cases
case (i) 0 < x < 1 0<x<1 0 < x < 1
Write x = 1 1 + h , h > 0 x=\displaystyle\frac{1}{1+h}, h>0 x = 1 + h 1 , h > 0
then x n = 1 ( 1 + h ) n ⩽ 1 1 + x h → 1 a > 1 b x^{n}=\displaystyle\frac{1}{(1+h)^{n}} \leqslant \frac{1}{1+x h} \quad \begin{array}{ll} & \rightarrow \frac{1}{a}>\frac{1}{b}\end{array} x n = ( 1 + h ) n 1 ⩽ 1 + x h 1 → a 1 > b 1
< 1 n h
<\frac{1}{n h}
< nh 1 Thus ∣ x n − 0 ∣ = ∣ x n ∣ = 1 ( 1 + h ) n < 1 n h < ε \left|x^{n}-0\right|=\left|x^{n}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{n h}<\varepsilon ∣ x n − 0 ∣ = ∣ x n ∣ = ( 1 + h ) n 1 < nh 1 < ε n h > 1 ε n h>\frac{1}{\varepsilon} nh > ε 1 x > 1 h ε x>\frac{1}{h \varepsilon} x > h ε 1 x ⩾ ⌈ 1 h ε ⌉ x \geqslant\left\lceil\frac{1}{h \varepsilon}\right\rceil x ⩾ ⌈ h ε 1 ⌉
for any ε > 0 \varepsilon>0 ε > 0
Thus ∀ ε > 0 , x x ∣ < ε \forall \varepsilon>0, \quad x^{x} \mid<\varepsilon \quad ∀ ε > 0 , x x ∣< ε
n ⩾ ⌈ 1 n ε ⌉ , x = 1 1 + h
n \geqslant\left\lceil\frac{1}{n \varepsilon}\right\rceil \quad, x=\frac{1}{1+h}
n ⩾ ⌈ n ε 1 ⌉ , x = 1 + h 1 case (ii) x = 0 , x n = 0 → 0 x=0, x^{n}=0 \rightarrow 0 x = 0 , x n = 0 → 0 x → + ∞ x \rightarrow+\infty x → + ∞
case (iii) − 1 < x < 0 -1<x<0 − 1 < x < 0
then 0 < − x < 1 0<-x<1 0 < − x < 1
and − x = 1 1 + h , h > 0 -x=\frac{1}{1+h}, h>0 − x = 1 + h 1 , h > 0
so
∣ x n − 0 ∣ = ∣ x x ∣ = 1 ( 1 + h ) n < 1 x h \left|x^{n}-0\right|=\left|x^{x}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{x h} ∣ x n − 0 ∣ = ∣ x x ∣ = ( 1 + h ) n 1 < x h 1
Exevise Show ( 1 ) (1) ( 1 ) ∣ x ∣ ⩾ 1 ⇒ lim n → + ∞ x n ≠ 0 |x| \geqslant 1 \Rightarrow \lim _{n \rightarrow+\infty} x^{n} \neq 0 ∣ x ∣ ⩾ 1 ⇒ lim n → + ∞ x n = 0
Returning to infinite series,
We say ∑ n = 0 + ∞ a n \sum_{n=0}^{+\infty} a_{n} ∑ n = 0 + ∞ a n L L L
and wite ∑ n = 0 + ∞ a n = L \sum_{n=0}^{+\infty} a_{n}=L ∑ n = 0 + ∞ a n = L
lim n → + ∞ S n = lim n → + ∞ ( ∑ k = 0 n a k ) = L
\lim _{n \rightarrow+\infty} S_{n}=\lim _{n \rightarrow+\infty}\left(\sum_{k=0}^{n} a_{k}\right)=L
n → + ∞ lim S n = n → + ∞ lim ( k = 0 ∑ n a k ) = L (14)
Thus an infinite series converges the sequence of partial sums converges to a limit.
If ∑ n = 0 + ∞ a n \sum_{n=0}^{+\infty} a_{n} ∑ n = 0 + ∞ a n
ie, lim n → + ∞ S n \lim _{n \rightarrow+\infty} S_{n} lim n → + ∞ S n
we say ∑ n = 0 + ∞ a n \sum_{n=0}^{+\infty} a_{n} ∑ n = 0 + ∞ a n
The Infinite Geometric Series
∑ k = 0 + ∞ a r k is convergent if and only if ∣ r ∣ < 1
\sum_{k=0}^{+\infty} a r^{k} \quad \text { is convergent if and only if }|r|<1
k = 0 ∑ + ∞ a r k is convergent if and only if ∣ r ∣ < 1 Since G n = ∑ k = 0 n a r k = a ( r n + 1 − 1 ) r − 1 G_{n}=\displaystyle\sum_{k=0}^{n} a r^{k}=\frac{a\left(r^{n+1}-1\right)}{r-1} G n = k = 0 ∑ n a r k = r − 1 a ( r n + 1 − 1 )
If ∣ r ∣ < 1 |r|<1 ∣ r ∣ < 1 lim n → + ∞ G n = lim n → + ∞ a ( r n + 1 − 1 ) r − 1 \displaystyle\lim _{n \rightarrow+\infty} G_{n}=\lim _{n \rightarrow+\infty} \frac{a\left(r^{n+1}-1\right)}{r-1} n → + ∞ lim G n = n → + ∞ lim r − 1 a ( r n + 1 − 1 )
= a ( 0 − 1 ) r − 1 = a 1 − r
\begin{aligned}
& =\frac{a(0-1)}{r-1} \\
& =\frac{a}{1-r}
\end{aligned}
= r − 1 a ( 0 − 1 ) = 1 − r a Thus for ∣ r ∣ < 1 , ∑ k = 0 + ∞ a r k = a 1 − r \displaystyle|r|<1, \sum_{k=0}^{+\infty} a r^{k}=\frac{a}{1-r} ∣ r ∣ < 1 , k = 0 ∑ + ∞ a r k = 1 − r a
Exercise: 0.999 ⋯ = 1 0.999 \cdots=1 0.999 ⋯ = 1
Exercise use this result to show 0.999 ⋯ = 1 0.999 \cdots=1 0.999 ⋯ = 1
0.9999 ⋯ = 9 10 + 9 100 + ⋯ = ∑ k = 1 ∞ 9 1 0 k = 9 ( ∑ k = 1 ∞ ( 1 10 ) k ) = 9 ( 1 10 + 1 1 0 2 + ⋯ + 1 1 0 n + 1 1 0 n + 1 + ⋯ ) = 9 10 ( 1 + 1 10 + 1 1 0 2 + ⋯ ) = 9 10 ∑ k = 0 ∞ ( 1 10 ) k = 9 10 1 1 − 1 10 = 9 10 ⋅ 1 ( 9 10 ) = 1
\begin{aligned}
0.9999 \cdots = \frac{9}{10} + \frac{9}{100} + \cdots & =\sum_{k=1}^{\infty} \frac{9}{10^{k}} \\
& =9\left(\sum_{k=1}^{\infty}\left(\frac{1}{10}\right)^{k}\right) \\
& =9\left(\frac{1}{10}+\frac{1}{10^{2}}+\cdots+\frac{1}{10^{n}}+\frac{1}{10^{n+1}}+\cdots\right) \\
& =\frac{9}{10}\left(1+\frac{1}{10}+\frac{1}{10^{2}}+\cdots\right) \\
& =\frac{9}{10} \sum_{k=0}^{\infty}\left(\frac{1}{10}\right)^{k}=\frac{9}{10} \frac{1}{1-\frac{1}{10}} \\
& =\frac{9}{10} \cdot \frac{1}{\left(\frac{9}{10}\right)}=1
\end{aligned}
0.9999 ⋯ = 10 9 + 100 9 + ⋯ = k = 1 ∑ ∞ 1 0 k 9 = 9 ( k = 1 ∑ ∞ ( 10 1 ) k ) = 9 ( 10 1 + 1 0 2 1 + ⋯ + 1 0 n 1 + 1 0 n + 1 1 + ⋯ ) = 10 9 ( 1 + 10 1 + 1 0 2 1 + ⋯ ) = 10 9 k = 0 ∑ ∞ ( 10 1 ) k = 10 9 1 − 10 1 1 = 10 9 ⋅ ( 10 9 ) 1 = 1 We have shown only the "If" part of own statement.
To prove the "only if " part, we note
for r = 1 , G n = a ( x + 1 ) → + ∞ r=1, G_{n}=a(x+1) \rightarrow+\infty r = 1 , G n = a ( x + 1 ) → + ∞ n → + ∞ n \rightarrow+\infty n → + ∞
so { G n } n = 0 + ∞ \left\{G_{n}\right\}_{n=0}^{+\infty} { G n } n = 0 + ∞ + ∞ +\infty + ∞ ∑ k = 0 + ∞ a ( 1 ) k \sum_{k=0}^{+\infty} a(1)^{k} ∑ k = 0 + ∞ a ( 1 ) k
If ∣ r ∣ > 1 |r|>1 ∣ r ∣ > 1 lim n → + ∞ ( r n + 1 ) \lim _{n \rightarrow+\infty}\left(r^{n+1}\right) lim n → + ∞ ( r n + 1 ) r > 1 r>1 r > 1 r < − 1 , r n + 1 r<-1, r^{n+1} r < − 1 , r n + 1
EXERCISE: What happens when r = − 1 r=-1 r = − 1
Principle of Mathematical Induction
Consider a formal sequence of propositional functions { P ( n ) } n = 1 + ∞ \{P(n)\}_{n=1}^{+\infty} { P ( n ) } n = 1 + ∞
We want to be able to prove that the proposition ∀ n P ( n ) \forall n P(n) ∀ n P ( n ) ∀ \forall ∀ Z + \mathbb{Z}^{+} Z +
As some examples of such a proposition we have the 3 summation formulae from before,
∑ k = 1 n k = n ( n + 1 ) 2 , ∀ n + Z + \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n+\mathbb{Z}^{+} k = 1 ∑ n k = 2 n ( n + 1 ) , ∀ n + Z + ¶
∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 , ∀ n ∈ Z + \sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z}^{+} k = 1 ∑ n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) , ∀ n ∈ Z + ¶
∑ k = 1 n k 3 = [ n ( n + 1 ) 2 ] 2 , ∀ n ∈ Z + \sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}, \forall n \in \mathbb{Z}^{+} k = 1 ∑ n k 3 = [ 2 n ( n + 1 ) ] 2 , ∀ n ∈ Z + ¶
We prove such universally quantified propositions using the principle of mathematical induction
Steps
principle of mathematical induction has 2 steps.
Step 1 Basis step; prove P ( 1 ) P(1) P ( 1 )
Step 2 Inductive step; prove that the proposition∀ k ( P ( k ) → P ( k + 1 ) ) ( k ≥ 1 ) \forall k(P(k) \rightarrow P(k+1)) \quad(k \geq 1) ∀ k ( P ( k ) → P ( k + 1 )) ( k ≥ 1 )
We will prove the validity of PMI. later
For now consider some examples. At the same time we will be proving useful and important results
Prove statement 1
Exercise Prove statement eq induction-1[ Note, we already gave a direct proof by showing P ( n ) is T , for all n ] \left[\begin{array}{c}\text { Note, we already gave a direct proof } \\ \text { by showing } P(n) \text { is } T \text {, for all } n\end{array}\right] [ Note, we already gave a direct proof by showing P ( n ) is T , for all n ]
Let P ( n ) P(n) P ( n )
∑ k = 1 n k = n ( n + 1 ) 2 = f ( n )
\sum_{k=1}^{n} k=\frac{n(n+1)}{2}=f(n)
k = 1 ∑ n k = 2 n ( n + 1 ) = f ( n ) Basis Step
P ( 1 ) : ∑ k = 1 1 k = 1 , f ( 1 ) = 1 ( 1 + 1 ) 2 = 1 \displaystyle P(1): \sum_{k=1}^{1} k=1, f(1)=\frac{1(1+1)}{2}=1 P ( 1 ) : k = 1 ∑ 1 k = 1 , f ( 1 ) = 2 1 ( 1 + 1 ) = 1
∴ P ( 1 ) \therefore P(1) ∴ P ( 1 )
Inductive step
assume P k ( k ) P_{k}(k) P k ( k ) k ∈ Z + ( k ⩾ 1 ) k \in \mathbb{Z}^{+}(k \geqslant 1) k ∈ Z + ( k ⩾ 1 )
That is ∑ l = 1 k l = k ( k + 1 ) 2 = f ( k ) \displaystyle\sum_{l=1}^{k} l=\frac{k(k+1)}{2}=f(k) l = 1 ∑ k l = 2 k ( k + 1 ) = f ( k )
We show now that P ( k + 1 ) P(k+1) P ( k + 1 )
ie, ∑ k = 1 k + 1 l = f ( k + 1 ) = ( k + 1 ) ( k + 2 ) 2 \displaystyle\sum_{k=1}^{k+1} l=f(k+1) =\frac{(k+1)(k+2)}{2} k = 1 ∑ k + 1 l = f ( k + 1 ) = 2 ( k + 1 ) ( k + 2 )
But
∑ l = 1 k + 1 l = ∑ ℓ = 1 k l + ( k + 1 ) = k ⋅ ( k + 1 ) 2 + ( k + 1 ) , by hypothesis. = ( k + 1 ) ( k 2 + 1 ) = ( k + 1 ) ( k + 2 ) 2 = f ( k + 1 )
\begin{aligned}
\sum_{l=1}^{k+1} l&=\sum_{\ell=1}^{k} l+(k+1) \\
& =\frac{k\cdot (k+1)}{2}+(k+1), \text { by hypothesis. } \\
& =(k+1)\left(\frac{k}{2}+1\right) \\
& =\frac{(k+1)(k+2)}{2}=f(k+1)
\end{aligned}
l = 1 ∑ k + 1 l = ℓ = 1 ∑ k l + ( k + 1 ) = 2 k ⋅ ( k + 1 ) + ( k + 1 ) , by hypothesis. = ( k + 1 ) ( 2 k + 1 ) = 2 ( k + 1 ) ( k + 2 ) = f ( k + 1 ) Thus P ( k ) → P ( k + 1 ) , ∀ k ∈ Z + P(k) \rightarrow P(k+1), \forall k \in \mathbb{Z}^{+} P ( k ) → P ( k + 1 ) , ∀ k ∈ Z +
Hence by P M I , ∑ k = 1 n k = n ( n + 1 ) 2 , ∀ n ∈ Z + \displaystyle P M I, \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n \in \mathbb{Z}^{+} PM I , k = 1 ∑ n k = 2 n ( n + 1 ) , ∀ n ∈ Z +
Prove Statement 2
Prove eq induction-2∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 , ∀ n ∈ Z \displaystyle\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z} k = 1 ∑ n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) , ∀ n ∈ Z = f ( x ) =f(x) = f ( x )
Basis Step
n = 1. ∑ k = 1 k 2 = 1 ; f ( 1 ) = 1 ( 2 ) ( 3 ) 6 = 1
n=1 . \quad \sum_{k=1} k^{2}=1 ; f(1)=\frac{1(2)(3)}{6}=1
n = 1. k = 1 ∑ k 2 = 1 ; f ( 1 ) = 6 1 ( 2 ) ( 3 ) = 1 Thus P ( 1 ) P(1) P ( 1 )
Inductive Step
Assume P ( k ) P(k) P ( k ) k ∈ Z + ( k ⩾ 1 ) k \in \mathbb{Z}^{+}(k \geqslant 1) k ∈ Z + ( k ⩾ 1 )
T h e n ∑ l = 1 k + 1 l 2 = ∑ l = 1 k l 2 + ( k + 1 ) 2 = k ( k + 1 ) ( 2 k + 1 ) 6 + ( k + 1 ) 2 , by hypothesis = ( k + 1 ) [ k ( 2 k + 1 ) 6 + k + 1 ] = ( k + 1 ) [ 2 k 2 + k + 6 ( k + 1 ) 6 ] = ( k + 1 ) [ 2 k 2 + 7 k + 6 6 ] = ( k + 1 ) 6 [ 2 k 2 + 4 k + 3 k + 6 ] = ( k + 1 ) 6 [ 2 k ( k + 2 ) + 3 ( k + 2 ) ] = ( k + 1 ) ( k + 2 ) ( 2 k + 3 ) 6 = f ( k + 1 )
\begin{aligned}
Then\quad\sum_{l=1}^{k+1} l^{2}&=\sum_{l=1}^{k} l^{2}+(k+1)^{2}\\
\newline
& =\frac{k(k+1)(2k+1)}{6}+(k+1)^{2} \text {, by hypothesis} \\
\newline
& =(k+1)\left[\frac{k(2 k+1)}{6}+k+1\right] \\
\newline
& =(k+1)\left[\frac{2k^{2}+k+6(k+1)}{6}\right] \\
\newline
& =(k+1)\left[\frac{2k^{2}+7k+6}{6}\right] \\
\newline
& =\frac{(k+1)}{6}\left[2k^{2}+4k + 3k+6\right] \\
\newline
& =\frac{(k+1)}{6}[2 k(k+2)+3(k+2)] \\
\newline
& =\frac{(k+1)(k+2)(2k+3)}{6}=f(k+1)
\end{aligned}
T h e n l = 1 ∑ k + 1 l 2 = l = 1 ∑ k l 2 + ( k + 1 ) 2 = 6 k ( k + 1 ) ( 2 k + 1 ) + ( k + 1 ) 2 , by hypothesis = ( k + 1 ) [ 6 k ( 2 k + 1 ) + k + 1 ] = ( k + 1 ) [ 6 2 k 2 + k + 6 ( k + 1 ) ] = ( k + 1 ) [ 6 2 k 2 + 7 k + 6 ] = 6 ( k + 1 ) [ 2 k 2 + 4 k + 3 k + 6 ] = 6 ( k + 1 ) [ 2 k ( k + 2 ) + 3 ( k + 2 )] = 6 ( k + 1 ) ( k + 2 ) ( 2 k + 3 ) = f ( k + 1 ) Thus ∀ k ∈ Z + , P ( k ) → P ( k + 1 ) \forall k \in \mathbb{Z}^{+},\quad P(k) \rightarrow P(k+1) ∀ k ∈ Z + , P ( k ) → P ( k + 1 ) principle of mathematical induction P ( n ) P(n) P ( n ) ∀ n + Z + \forall n+\mathbb{Z}^{+} ∀ n + Z +
Common Errors
Note
A common error in proofs using principle of mathematical induction that lead to an invalid conclusion occurs in the inductive step when we prove P ( k ) → P ( k + 1 ) P(k) \rightarrow P(k+1) P ( k ) → P ( k + 1 ) k = 2 , 3 , 4 , … k=2,3,4, \ldots k = 2 , 3 , 4 , … not k = 1 k=1 k = 1 k > 1 k>1 k > 1 P ( k ) → P ( k + 1 ) P(k) \rightarrow P(k+1) P ( k ) → P ( k + 1 ) P ( 2 ) P(2) P ( 2 ) ∀ n P ( n ) \forall n P(n) ∀ n P ( n )
We may use P M I P M I PM I ∀ n ⩾ n 0 , P ( n ) \forall n \geqslant n_{0}, P(n) ∀ n ⩾ n 0 , P ( n ) n 0 > 1 n_{0}>1 n 0 > 1 P ( n 0 ) P\left(n_{0}\right) P ( n 0 ) ∀ k ⩾ n 0 , P ( k ) → P ( k + 1 ) \forall k \geqslant n_{0}, P(k) \rightarrow P(k+1) ∀ k ⩾ n 0 , P ( k ) → P ( k + 1 )
The Harmonic Progression
Recall the Harmonic Progression { a n } n = 1 ∞ \left\{a_{n}\right\}_{n=1}^{\infty} { a n } n = 1 ∞ a n = 1 n a_{n}=\frac{1}{n} a n = n 1
Even though,
lim n → + ∞ a n = lim n → + ∞ 1 n = 0 ,
\lim _{n \rightarrow+\infty} a_{n}=\lim _{n \rightarrow+\infty} \frac{1}{n}=0 \text {, }
n → + ∞ lim a n = n → + ∞ lim n 1 = 0 , the Harmonic series ∑ n = 1 + ∞ 1 n = 1 + 1 2 + 1 3 + ⋯ + 1 n + ⋯ \displaystyle\sum_{n=1}^{+\infty} \frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}+\cdots n = 1 ∑ + ∞ n 1 = 1 + 2 1 + 3 1 + ⋯ + n 1 + ⋯ The smaller and smaller bit added infinitely often add up to + ∞ +\infty + ∞
We will use the principle of mathematical induction to help prove this fact
Lemma Let $H_{n}=\sum_{k=1}^{n} \frac{1}{k}$.
Then $H_{2^n} \geqslant 1+\frac{n}{2}=f(x), \forall n \in \mathbb{Z}^{+}$
bdg-secondary Proof
Basis step
n = 1 H 2 1 = 1 + 1 2 = f ( 1 ) ∴ H 2 1 ⩾ f ( 1 )
\begin{aligned}
& n=1 \\
& H_{2^{1}}=1+\frac{1}{2}=f(1) \quad \therefore H_{2^1} \geqslant f(1)
\end{aligned}
n = 1 H 2 1 = 1 + 2 1 = f ( 1 ) ∴ H 2 1 ⩾ f ( 1 ) Inductive Step
assume H 2 k ⩾ 1 + k 2 , ∀ k ∈ Z + H_{2^{k}} \geqslant 1+\frac{k}{2}, \forall k \in \mathbb{Z}^{+} H 2 k ⩾ 1 + 2 k , ∀ k ∈ Z +
Then
H 2 k + 1 = ∑ k = 1 2 k + 1 1 k = ∑ r = 1 2 k 1 r + ∑ k = 2 k + 1 2 k + 1 1 r ⩾ 1 + k 2 + 1 2 k + 1 + 1 2 k + 2 + ⋯ + 1 2 k + 1 = 1 + k 2 + 1 2 k + 1 + 1 2 k + 2 + ⋯ + 1 2 k + 2 k
\begin{aligned}
H_{2^{k+1}} & =\sum_{k=1}^{2^{k+1}} \frac{1}{k}=\sum_{r=1}^{2^{k}} \frac{1}{r}+\sum_{k=2^{k}+1}^{2^{k+1}} \frac{1}{r} \\
& \geqslant 1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k+1}} \\
& =1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k}+2^{k}}
\end{aligned}
H 2 k + 1 = k = 1 ∑ 2 k + 1 k 1 = r = 1 ∑ 2 k r 1 + k = 2 k + 1 ∑ 2 k + 1 r 1 ⩾ 1 + 2 k + 2 k + 1 1 + 2 k + 2 1 + ⋯ + 2 k + 1 1 = 1 + 2 k + 2 k + 1 1 + 2 k + 2 1 + ⋯ + 2 k + 2 k 1 ⩾ 1 + k 2 + { 1 2 k + 2 k + ⋯ + 2 k terms 2 k + 2 k } ( make the bottom bigger fraction get smaller ) = 1 + k 2 + 2 k ⋅ 1 2 k + 1 = 1 + k 2 + 1 2 = 1 + k + 1 2 = f ( k + 1 )
\begin{aligned}
& \geqslant 1+\frac{k}{2}+\left\{\frac{1}{2^{k}+2^{k}}+\cdots+\frac{2^{k} \text { terms }}{2^{k}+2^{k}}\right\} \quad\left(\begin{array}{l}
\text { make the } \\
\text { bottom bigger } \\
\text { fraction get } \\
\text { smaller }
\end{array}\right) \\
& =1+\frac{k}{2}+2^{k} \cdot \frac{1}{2^{k+1}}=1+\frac{k}{2}+\frac{1}{2}=1+\frac{k+1}{2}=f(k+1)
\end{aligned}
⩾ 1 + 2 k + { 2 k + 2 k 1 + ⋯ + 2 k + 2 k 2 k terms } ⎝ ⎛ make the bottom bigger fraction get smaller ⎠ ⎞ = 1 + 2 k + 2 k ⋅ 2 k + 1 1 = 1 + 2 k + 2 1 = 1 + 2 k + 1 = f ( k + 1 ) Thus by P,M.1. H 2 n ⩾ 1 + n 2 , ∀ n ∈ Z + H_{2} n \geqslant 1+\frac{n}{2}, \forall n \in \mathbb{Z}^{+} H 2 n ⩾ 1 + 2 n , ∀ n ∈ Z +
Now the sequence
{ H n } n = 1 ∞ \left\{H_{n}\right\}_{n=1}^{\infty} { H n } n = 1 ∞
because H n + 1 = H n + 1 n + 1 > H n H_{n+1}=H_{n}+\frac{1}{n+1}>H_{n} H n + 1 = H n + n + 1 1 > H n
Also the subsequence
{ H 2 n } x = 1 ∞ \left\{H_{2^{n}}\right\}_{x=1}^{\infty} { H 2 n } x = 1 ∞
the lemma, has
lim x → + ∞ H 2 x = + ∞
\lim _{x \rightarrow+\infty} H_{2 x}=+\infty
x → + ∞ lim H 2 x = + ∞ These two facts allow us to assent that
lim n → + ∞ H n = + ∞ and the
\lim _{n \rightarrow+\infty} H_{n}=+\infty \text { and the }
n → + ∞ lim H n = + ∞ and the hamonic series is divergent
Exerciser) Use PMI to prove that 3 / 2 2 n − 1 , ∀ x ∈ Z + 3 / 2^{2 n}-1, \forall x \in \mathbb{Z}^{+} 3/ 2 2 n − 1 , ∀ x ∈ Z +
Prove summation formula (3)
P351 #32 3 ∣ n 3 + 2 n ∀ n ⩾ 1 3 \mid n^{3}+2 n \quad \forall n \geqslant 1 3 ∣ n 3 + 2 n ∀ n ⩾ 1
23
P ( n ) : 3 ∣ n 3 + 2 n P(n): 3 \mid n^{3}+2 n \quad P ( n ) : 3 ∣ n 3 + 2 n ∀ n ⩾ 1 P ( n ) \quad \forall n \geqslant 1 P(n) ∀ n ⩾ 1 P ( n )
Basis step
Let n = 1 , n 3 + 2 n = 1 + 2 = 3 + 3 / 3 n=1, n^{3}+2 n=1+2=3+3 / 3 n = 1 , n 3 + 2 n = 1 + 2 = 3 + 3/3
∴ P ( 1 ) \therefore P(1) ∴ P ( 1 )
Inductive Step
want to show
∀ k ⩾ 1 P ( k ) → P ( k + 1 ) \forall k \geqslant 1 \quad P(k) \rightarrow P(k+1) \quad ∀ k ⩾ 1 P ( k ) → P ( k + 1 )
Assume 31 k 3 + 2 k 31 k^{3}+2 k 31 k 3 + 2 k P ( k ) P(k) P ( k )
Then ( k 0 + 1 ) 3 + 2 ( k + 1 ) = k 3 + 3 k 2 + 3 k + 1 \left(k^{0}+1\right)^{3}+2(k+1)=k^{3}+3 k^{2}+3 k+1 ( k 0 + 1 ) 3 + 2 ( k + 1 ) = k 3 + 3 k 2 + 3 k + 1
= k 3 + 2 k + 3 k + 2 = k 3 + 2 k divisible by + 3 ( k 2 + k + 1 ) divisible by 3
\begin{aligned}
= & k^{3}+2 k+3 k+2 \\
= & \frac{k^{3}+2 k}{\text { divisible }_{\text {by }}}+\frac{3\left(k^{2}+k+1\right)}{\text { divisible by } 3}
\end{aligned}
= = k 3 + 2 k + 3 k + 2 divisible by k 3 + 2 k + divisible by 3 3 ( k 2 + k + 1 ) by hypothein
∴ P ( k + 1 ) \therefore P(k+1) ∴ P ( k + 1 )
